/*
提交链接：https://leetcode.cn/problems/edit-distance/description/
72.编辑距离
王顶成 2024/9/19
*/



class Solution {
public:
    int minDistance(string word1, string word2) {
        int w1=word1.size();
        int w2=word2.size();
        if(w1*w2==0) return w1+w2;
        vector<vector<int>> a(w1+1,vector<int>(w2+1));
        for(int i=0;i<w1+1;i++) a[i][0]=i;
        for(int i=0;i<w2+1;i++) a[0][i]=i;

        for(int i=1;i<w1+1;i++){
            for(int j=1;j<w2+1;j++){
                int l=a[i-1][j-1];
                if(word1[i-1]!=word2[j-1]) l+=1;
                a[i][j]=min(a[i-1][j]+1,min(a[i][j-1]+1,l));
            }
        }
        return a[w1][w2];
    }
};